#!/usr/bin/env python


import operator
from collections import defaultdict
import itertools
import logging
import math
from util import *



class Predictor(object):
    def __init__(self, data, options):
    	self.options = options
        self.data = data
        self.precompute()
    
    def precompute(self):
        """
        Given some training data, precompute anything that would be useful for making
        predictions later.
        
        does not return anything
        """
        pass

    def predict(self, user_id, movie_id):
        """
        Return a prediction for how much this user would like this movie, as a float
        between 1.0 and 5.0
        """
        return 3.0

class AverageBased(Predictor):
    """A silly predictor that always predicts the average rating."""
    def precompute(self):
        n = float(len(self.data))
        self.avg = mean(t[2] for t in self.data)
    
    def predict(self, user_id, movie_id):
        return self.avg

class UserAverageBased(Predictor):
    """A marginally less silly predictor that always predicts the user's average rating."""

    # An example of how to save precomputed info
    def precompute(self):
        self.user_avg_rating = {}  # uid -> average prediction by uid
        for uid, group in itertools.groupby(self.data, key=operator.itemgetter(0)):
            u_pred = list(group)
            self.user_avg_rating[uid] = mean([t[2] for t in u_pred])

    
    def predict(self, user_id, movie_id):
        return self.user_avg_rating[user_id]


class UserBased(Predictor):
    """
    data = [(uid, movie_id, pred)]
    """
    
    def precompute(self):
        # Compute all pairs similarity between users, and find the N most similar
        # users to each
        self.user_predictions = {}  # uid -> dict: movie_id -> pred
        self.user_avg_rating = {}  # uid -> average prediction by uid
        self.user_rated = {}  # uid -> set of (movie ids rated by uid)
        self.similarities = defaultdict(list) # uid -> list of (uid2, similarity)
        self.counter = 0

 
        # group data items by user so we can compute things
        self.data.sort()
  
        for uid, group in itertools.groupby(self.data, key=operator.itemgetter(0)):
            
            u_pred = list(group)
            
            #user_predictions
            dict_movieID_pred = {}
            for x in range(0,len(u_pred)):
                dict_movieID_pred[u_pred[x][1]] = u_pred[x][2]
            self.user_predictions[uid] = (dict_movieID_pred)
            
            #user_avg_rating
            self.user_avg_rating[uid] = mean([p[2] for p in u_pred]) 
            
            #user_rated
            rated_movies = []
            for x in range(0,len(u_pred)):
                rated_movies.append(u_pred[x][1])
            self.user_rated[uid] = rated_movies

        N = self.options.N
        #print 'user rated: %s' %self.user_rated
        #print 'user avg rating: %s' %self.user_avg_rating
        #print 'user predictions: %s' %self.user_predictions    


        def similarity(u1, u2):
            # Compute the pearson correlation (notes -- Eq 16.2)
            # numerator and divisor are calculated separately for each movie that is rated by both agents
            numerator = 0.0
            divisor_1 = 0.0
            divisor_2 = 0.0
            
            # iterate over all movies (j)
            movies_by_u1 = self.user_rated.get(u1)
            movies_by_u2 = self.user_rated.get(u2)
            
            for x in range(0, len(movies_by_u1)):
                #if a movie is rated by u1 and u2 then add it to the numerator and divisor according to formula in script
                movie = movies_by_u1[x]
                if movie in movies_by_u2:
                    part_1 = (self.user_predictions.get(u1)).get(movie) - self.user_avg_rating.get(u1)
                    part_2 = (self.user_predictions.get(u2)).get(movie) - self.user_avg_rating.get(u2)
                    numerator += (part_1*part_2)
                    divisor_1 += (part_1*part_1)
                    divisor_2 += (part_2*part_2)       
            divisor_1 = math.sqrt(divisor_1)
            divisor_2 = math.sqrt(divisor_2)
            divisor = divisor_1 * divisor_2
            
            #if divisor is 0, then similarity = 0
            if(divisor == 0.0):
                return 0.0
            else:
                return (numerator / divisor)

        
        #iterate over all users, compute similarity and store it 
        for i_1 in range(0, len(self.user_avg_rating)):
            for i_2 in range((i_1+1), len(self.user_avg_rating)):
                #compute similarity of those two users
                res = similarity(i_1+1, i_2+1)
                #we cannot use similarities smaller than 0, so we set all similarities <= 0 to 0
                #we also use here that the similarity between 1 and 2 is symmetric.
                if (res <= 0):
                    self.similarities.setdefault(i_1+1, []).append([i_2+1, 0.0])
                    self.similarities.setdefault(i_2+1, []).append([i_1+1, 0.0])
                else: 
                    self.similarities.setdefault(i_1+1, []).append([i_2+1, res])
                    self.similarities.setdefault(i_2+1, []).append([i_1+1, res])
        
        #iterate over all users in order to truncate the result to N
        for i in range(0, len(self.user_avg_rating)):
            other_users = self.similarities.get(i+1) #all users and their similarity for user i
            
            #sort users according to their similarity value
            other_users = sorted(other_users, key=lambda val: val[1])
            
            #remove similar users until at most N users are similar
            while(not(len(other_users)<=N)):
                other_users.remove(other_users[0])
            
            del self.similarities[i+1]
            for j in range(0, len(other_users)):
                self.similarities.setdefault(i+1, []).append([other_users[j][0], other_users[j][1]])

                

        #logging.debug("Similarities: ")
        #logging.debug(self.similarities)
        
        
        
    
    def predict(self, user_id, movie_id):

        r = self.user_avg_rating[user_id]
        
        #simple averaging method
        sim_users = self.similarities.get(user_id)      
        n = 0.0
        avg_rating = 0.0
        for i in range(0, len(sim_users)):
            if movie_id in self.user_rated.get(sim_users[i][0]):
                n += 1
                avg_rating += self.user_predictions.get(sim_users[i][0]).get(movie_id)
        if n==0:
            return r
        else:
            return 1/n * avg_rating
    
        print 'here'
        #weighted sum aggregation
        sim_users = self.similarities.get(user_id)     
        numerator = 0.0
        denominator = 0.0
        for i in range(0, len(sim_users)):
            if movie_id in self.user_rated.get(sim_users[i][0]):
                user = sim_users[i][0]
                numerator += sim_users[i][1]  * (self.user_predictions.get(user).get(movie_id))
                denominator += sim_users[i][1]
        
        if denominator == 0: #if denominator is 0, we jsut use the average
            return r
        else:
            return numerator/denominator
        
        #adjusted weighted sum aggregation
        #sim_users = self.similarities.get(user_id)#neighborhood of user_id
        #numerator = 0.0
        #denominator = 0.0
        #
        #for i in range(0, len(sim_users)):
        #    if movie_id in self.user_rated.get(sim_users[i][0]):
        #        user = sim_users[i][0]
        #        numerator += sim_users[i][1]  * (self.user_predictions.get(user).get(movie_id)-self.user_avg_rating.get(user))
        #        denominator += sim_users[i][1]
        
      

        #if divisor is 0, then we just use r as prediction
        if(denominator <= 0.0):
            return r
        else: 
            return r + (numerator / denominator)
        


class ItemBased(Predictor):
    
    def precompute(self):
        self.movie_rated = {} #movie_id -> list of user that rated this movie
        self.movie_average = {} #user_id -> avg rating (by all
        self.user_avg_rating = {}  # uid -> average prediction by uid
        self.user_rated = {}  # uid -> set of (movie ids rated by uid)
        self.user_predictions = {}  # uid -> dict: movie_id -> pred
        self.similarities = defaultdict(list) # mid -> list of (mid2, similarity)
        

        #sort data according to movies
        self.data = sorted(self.data, key=operator.itemgetter(1))
        
        #iterate over data, grouped by movie id
        for mid, group in itertools.groupby(self.data, key=operator.itemgetter(1)):
            movie_list = list(group)
            
            #for each movie a list with the user_ids that rated it
            self.movie_rated[mid] = list(p[0] for p in movie_list)
        
        
        self.data = sorted(self.data, key=operator.itemgetter(0))

        
        for uid, group in itertools.groupby(self.data, key=operator.itemgetter(0)):
            u_pred = list(group)
            
            #user_avg_rating
            self.user_avg_rating[uid] = mean([p[2] for p in u_pred]) 
            
            #user_rated
            rated_movies = []
            for x in range(0,len(u_pred)):
                rated_movies.append(u_pred[x][1])
            self.user_rated[uid] = rated_movies
            
            #user_predictions
            dict_movieID_pred = {}
            for x in range(0,len(u_pred)):
                dict_movieID_pred[u_pred[x][1]] = u_pred[x][2]
            self.user_predictions[uid] = (dict_movieID_pred)
        
        #adjusted cosine similarity
        def similarity(m1, m2):

                       
            numerator = 0.0
            denominator_1 = 0.0
            denominator_2 = 0.0
            
            #iterate over all users that rated both m1 and m2
            a = self.movie_rated.get(m1)
            b = self.movie_rated.get(m2)
            if a == None or b == None:
                return 0.0
            
            union_of_users = list(set(a) & set(b))
            
            for i in range(0, len(union_of_users)):
                user = union_of_users[i]
                r_i_m1 = self.user_predictions.get(user).get(m1)
                r_i_m2 = self.user_predictions.get(user).get(m2)
                r_i_avg = self.user_avg_rating.get(user)
                
                numerator += (r_i_m1-r_i_avg) * (r_i_m2-r_i_avg)
                denominator_1 += (r_i_m1-r_i_avg) * (r_i_m1-r_i_avg)
                denominator_2 += (r_i_m2-r_i_avg) * (r_i_m2-r_i_avg)
                
            
            denominator = math.sqrt(denominator_1) * math.sqrt(denominator_2)
            
            if denominator <= 0.0: #we don't want negative values and 0 is also not good to divide with 
                return 0.0 
            else:
                return numerator / denominator
        
        #cosine based similarity
        def similarity_cosine_based(m1, m2):

            
            nominator = 0.0
            denominator_1 = 0.0
            denominator_2 = 0.0
            
            #iterate over all users that rated both m1 and m2
            a = self.movie_rated.get(m1)
            b = self.movie_rated.get(m2)
            if a == None or b == None:
                return 0.0
            
            union_of_users = list(set(a) & set(b))
            
            #compute formula from script
            for i in range(0, len(union_of_users)):
                nominator += self.user_predictions.get(union_of_users[i]).get(m1)*self.user_predictions.get(union_of_users[i]).get(m2)
                denominator_1 += self.user_predictions.get(union_of_users[i]).get(m1)*self.user_predictions.get(union_of_users[i]).get(m1)
                denominator_2 += self.user_predictions.get(union_of_users[i]).get(m2)*self.user_predictions.get(union_of_users[i]).get(m2)
            
           
            denominator = math.sqrt(denominator_1)*math.sqrt(denominator_2)
            
            if(denominator<=0.0): #if denominator <=0, sim = 0 (we don't want negative values)
                return 0.0          
             
            return nominator/denominator
            
        
        #iterate over all movies, compute similarity and store it 
        for i_1 in range(0, len(self.movie_rated)):
            for i_2 in range((i_1+1), len(self.movie_rated)):
                res = similarity(i_1+1, i_2+1)
                #res = similarity_cosine_based(i_1+1, i_2+1)
                self.similarities.setdefault(i_1+1, []).append([i_2+1, res])
                self.similarities.setdefault(i_2+1, []).append([i_1+1, res])
        
        N = self.options.N
            
        #iterate over all movies and truncate to neighborhood N
        for i in range(0, len(self.movie_rated)):
            movies = self.similarities.get(i+1) 
            #truncate similarities to defined neighborhood
            movies = sorted(movies, key=lambda val: val[1])
            
            while(not(len(movies)<=N)):
                movies.remove(movies[0])
            
            del self.similarities[i+1]
            
           
            for j in range(0, len(movies)):
                self.similarities.setdefault(i+1, []).append([movies[j][0], movies[j][1]])
                 
    
    def predict(self, user_id, movie_id):
        
        user_pred = self.user_predictions.get(user_id) #movies that user_id rated (movie plus rating)
        movie_sim = self.similarities.get(movie_id) #similar movies  to movie_id
        
        numerator = 0.0
        denominator = 0.0
        
        for i in range(0, len(movie_sim)):
            if movie_sim[i][0] in user_pred:
                if not movie_sim[i][1] <= 0:
                    numerator += movie_sim[i][1]*user_pred.get(movie_sim[i][0])
                    denominator += movie_sim[i][1] 
        
        # return numerator /denominator
        if denominator == 0:
            return self.user_avg_rating.get(user_id)
        return numerator/denominator


class MagicBased(Predictor):
    """
    data = [(uid, movie_id, pred)]
    """
    
    def precompute(self):
        # Compute all pairs similarity between users, and find the N most similar
        # users to each
        self.user_predictions = {}  # uid -> dict: movie_id -> pred
        self.user_avg_rating = {}  # uid -> average prediction by uid
        self.user_rated = {}  # uid -> set of (movie ids rated by uid)
        self.similarities = defaultdict(list) # uid -> list of (uid2, similarity)
        self.counter = 0

 
        # group data items by user so we can compute things
        self.data.sort()
  
        for uid, group in itertools.groupby(self.data, key=operator.itemgetter(0)):
            
            u_pred = list(group)
            
            #user_predictions
            dict_movieID_pred = {}
            for x in range(0,len(u_pred)):
                dict_movieID_pred[u_pred[x][1]] = u_pred[x][2]
            self.user_predictions[uid] = (dict_movieID_pred)
            
            #user_avg_rating
            self.user_avg_rating[uid] = mean([p[2] for p in u_pred]) 
            
            #user_rated
            rated_movies = []
            for x in range(0,len(u_pred)):
                rated_movies.append(u_pred[x][1])
            self.user_rated[uid] = rated_movies

        N = self.options.N        
        

        def similarity(u1, u2):
            #print 'test for user %s and %s' %(u1, u2)
            
            #define some useful variables
            R_max = 5.0
            R_min = 1.0
            movies_by_u1 = self.user_rated.get(u1)
            movies_by_u2 = self.user_rated.get(u2)
            
            
            #c(v,u) = sum over all movies both users rated --> (1-(R_max - R_min)*abs(r_u1-r_u2)
            c = 0.0
            n = 0
            for x in range(0, len(movies_by_u1)):
                movie = movies_by_u1[x]
                if movie in movies_by_u2:
                    #print 'similar movie: %s' %movie
                    #movie has been rated by both users and therefore c has to be adapted
                    c += 1- (R_max-R_min)*abs(self.user_predictions.get(u1).get(movie)-self.user_predictions.get(u2).get(movie))
                    #print abs(self.user_predictions.get(u1).get(movie)-self.user_predictions.get(u2).get(movie))
                    n+=1
                    #print 'c: %s' %c
            
            #d(v,u) = (Nv-n)+(Nu-n) where Nv is the number of rated movies by user v and n the number of movies rated by both users
            N_u1 =  len(self.user_predictions.get(u1))
            N_u2 = len(self.user_predictions.get(u2))
            d = (N_u1-n)+(N_u2-n)
            
            #print 'Nu1: %s, Nu2: %s, n: %s, d: %s' %(N_u1, N_u2, n, d)
            
            #similarity = (e^(alpha*c(v,u)) -1)/(e^(alpha*c(v,u))+e^(beta*d(v,u))-2)
            #alpha = 0.01 beta = 0.0015
            sim = (math.exp(0.01*c)-1) / ( math.exp(0.01*c)+math.exp(0.015*d)-2)
            #print 'sim: %s' %sim
            
            return sim

        
        #iterate over all users, compute similarity and store it 
        for i_1 in range(0, len(self.user_avg_rating)):
            for i_2 in range((i_1+1), len(self.user_avg_rating)):
                #compute similarity of those two users
                res = similarity(i_1+1, i_2+1)
                #we cannot use similarities smaller than 0, so we set all similarities <= 0 to 0
                #we also use here that the similarity between 1 and 2 is symmetric.
                if (res <= 0):
                    self.similarities.setdefault(i_1+1, []).append([i_2+1, 0.0])
                    self.similarities.setdefault(i_2+1, []).append([i_1+1, 0.0])
                else: 
                    self.similarities.setdefault(i_1+1, []).append([i_2+1, res])
                    self.similarities.setdefault(i_2+1, []).append([i_1+1, res])
        
        #iterate over all users in order to truncate the result to N
        print len(self.similarities)
        for i in range(0, len(self.user_avg_rating)):
            other_users = self.similarities.get(i+1) #all users and their similarity for user i
            
            #sort users according to their similarity value
            other_users = sorted(other_users, key=lambda val: val[1])
            
            #remove similar users until at most N users are similar
            while(not(len(other_users)<=N)):
                other_users.remove(other_users[0])
            
            #del self.similarities[i+1]
            for j in range(0, len(other_users)):
                self.similarities.setdefault(i+1, []).append([other_users[j][0], other_users[j][1]])
        
    
    def predict(self, user_id, movie_id):

        r = self.user_avg_rating[user_id]
        
        
        
        #adjusted weighted sum aggregation
        sim_users = self.similarities.get(user_id)#neighborhood of user_id
        numerator = 0.0
        denominator = 0.0
        
        for i in range(0, len(sim_users)):
            if movie_id in self.user_rated.get(sim_users[i][0]):
                user = sim_users[i][0]
                numerator += sim_users[i][1]  * (self.user_predictions.get(user).get(movie_id)-self.user_avg_rating.get(user))
                denominator += sim_users[i][1]
        
      

        #if divisor is 0, then we just use r as prediction
        if(denominator <= 0.0):
            return r
        else: 
            return r + (numerator / denominator)
        


